package 字符串;

/**
 * 找出字符串中第一个匹配项的下标
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
 *
 * 思路：
 *  除了使用暴力匹配方法外，还可以使用KMP算法
 *
 *  KMP算法是一种改进的字符串匹配算法，能够在O(n + m)的时间复杂度内完成匹配，其中n是haystack的长度，m是needle的长度。

    解题思路
    构建部分匹配表（Partial Match Table）：这个表记录了模式串中每个位置的最大前缀后缀长度。
    匹配过程：
    使用两个指针分别指向haystack和needle。
    当字符匹配时，两个指针同时向前移动。
    当字符不匹配时，根据部分匹配表调整needle指针的位置，而不回退haystack指针。
    匹配成功：当needle指针到达末尾时，返回对应的haystack起始位置。
    未找到：如果遍历完haystack仍未找到needle，则返回 -1。
 *
 */
public class L_28 {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0; // 如果needle为空，返回0

        int m = haystack.length();
        int n = needle.length();
        int[] lps = computeLPS(needle);

        int i = 0; // 指向haystack
        int j = 0; // 指向needle

        while (i < m) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }

            if (j == n) {
                return i - j; // 匹配成功，返回起始位置
            } else if (i < m && haystack.charAt(i) != needle.charAt(j)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // 未找到，返回-1
    }

    /**
     * 计算KMP算法中的最长前缀后缀（LPS）数组
     * LPS数组用于描述模式串中每个位置之前的最长相同前后缀的长度
     * 这个函数对理解KMP算法的高效字符串匹配过程至关重要
     *
     * @param pattern 模式字符串，即我们需要构建LPS数组的字符串
     * @return 返回一个int数组，其中每个索引位置的值代表到该位置为止的最长相同前后缀的长度
     */
    private static int[] computeLPS(String pattern) {
      // 初始化变量
        int length = 0;
        int i = 1;
        int len = pattern.length();
        int[] lps = new int[len];
        lps[0] = 0; // 第一个字符的最长相同前后缀长度为0

        // 遍历模式串以填充LPS数组
        while (i < len) {
            // 当前字符与当前长度对应字符匹配时，增加长度并更新LPS数组
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                // 当前字符不匹配时，如果长度不为0，则更新长度为上一个长度对应的LPS值
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    // 如果长度为0且字符不匹配，则当前字符的最长相同前后缀长度为0，并移动到下一个字符
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps; // 返回计算好的LPS数组
    }
}
